{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Destroying Asteroids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: asteroidsDestroyed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #摧毁小行星"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>mass</code>&nbsp;，它表示一颗行星的初始质量。再给你一个整数数组&nbsp;<code>asteroids</code>&nbsp;，其中&nbsp;<code>asteroids[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;颗小行星的质量。</p>\n",
    "\n",
    "<p>你可以按 <strong>任意顺序</strong>&nbsp;重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 <strong>大于等于</strong>&nbsp;小行星的质量，那么小行星被 <strong>摧毁</strong>&nbsp;，并且行星会 <strong>获得</strong>&nbsp;这颗小行星的质量。否则，行星将被摧毁。</p>\n",
    "\n",
    "<p>如果所有小行星 <strong>都</strong>&nbsp;能被摧毁，请返回 <code>true</code>&nbsp;，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>mass = 10, asteroids = [3,9,19,5,21]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>一种安排小行星的方式为 [9,19,5,3,21] ：\n",
    "- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19\n",
    "- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38\n",
    "- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43\n",
    "- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46\n",
    "- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67\n",
    "所有小行星都被摧毁。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>mass = 5, asteroids = [4,9,23,4]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>\n",
    "行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。\n",
    "行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。\n",
    "它比 23 小，所以无法摧毁最后一颗小行星。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= mass &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= asteroids.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= asteroids[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [destroying-asteroids](https://leetcode.cn/problems/destroying-asteroids/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [destroying-asteroids](https://leetcode.cn/problems/destroying-asteroids/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n[3,9,19,5,21]', '5\\n[4,9,23,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort(reverse=True)\n",
    "        while asteroids:\n",
    "            x = asteroids.pop()\n",
    "            if x > mass:\n",
    "                return False\n",
    "            mass += x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, a: int, b: List[int]) -> bool:\n",
    "        b.sort(reverse=True)\n",
    "        while b:\n",
    "            t = b.pop()\n",
    "            if t<=a:\n",
    "                a+=t \n",
    "            else:\n",
    "                return False \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()   # 按照质量升序排序\n",
    "        for asteroid in asteroids:\n",
    "            # 按顺序遍历小行星，尝试摧毁并更新质量或者返回结果\n",
    "            if mass < asteroid:\n",
    "                return False\n",
    "            mass += asteroid\n",
    "        return True   # 成功摧毁所有小行星\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids):\n",
    "        asteroids=sorted(asteroids)\n",
    "        for i in asteroids:\n",
    "            if mass>=i:\n",
    "                mass+=i\n",
    "            else:\n",
    "                return False\n",
    "        return  True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "\n",
    "        for i in range(len(asteroids)):\n",
    "            if mass >= asteroids[i]:\n",
    "                mass += asteroids[i]\n",
    "\n",
    "                if mass >= asteroids[-1]:\n",
    "                    return True\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        sum_ = mass\n",
    "        for i in asteroids:\n",
    "            if sum_ < i:\n",
    "                return False\n",
    "            sum_ += i\n",
    "            if sum_ >= asteroids[-1]: return True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        flag = True \n",
    "        asteroids.sort()\n",
    "        for x in asteroids:\n",
    "            if mass < x:\n",
    "                flag = False \n",
    "                break \n",
    "            mass += x \n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for star in asteroids:\n",
    "            if mass >= star:\n",
    "                mass += star\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for x in asteroids:\n",
    "            if x > mass:\n",
    "                return False\n",
    "            mass += x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for x in asteroids:\n",
    "            if mass >= x:\n",
    "                mass += x\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in asteroids:\n",
    "            if mass < i: return False\n",
    "            else: mass += i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i,m in enumerate(asteroids):\n",
    "            if mass < m:\n",
    "                return False\n",
    "            mass += m \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for m in asteroids:\n",
    "            if mass > asteroids[-1]:\n",
    "                return True\n",
    "            if mass < m:\n",
    "                return False\n",
    "            mass += m \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in range(len(asteroids)):\n",
    "            if mass < asteroids[i]:\n",
    "                return False\n",
    "            mass += asteroids[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in range(len(asteroids)):\n",
    "            if mass<asteroids[i]:\n",
    "                return False\n",
    "            mass+=asteroids[i]\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "\n",
    "        asteroids.sort()\n",
    "\n",
    "        for a in asteroids:\n",
    "            if a <= mass:\n",
    "                mass += a\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in asteroids:\n",
    "            if mass >= i:\n",
    "                mass += i\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "\n",
    "        for i in range(len(asteroids)):\n",
    "            if mass >= asteroids[i]:\n",
    "                mass += asteroids[i]\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, arr: List[int]) -> bool:\n",
    "        arr = sorted(arr)\n",
    "        for x in arr:\n",
    "            if mass >= x:\n",
    "                mass += x\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        m = mass\n",
    "        for i in asteroids:\n",
    "            if i > m:return False\n",
    "            m += i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for asteroid in asteroids:\n",
    "            if mass >= asteroid:\n",
    "                mass += asteroid\n",
    "            else:\n",
    "                return False \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        if mass >= max(asteroids):\n",
    "            return True\n",
    "        \n",
    "        asteroids.sort()\n",
    "        for i in asteroids:\n",
    "            if mass >= i:\n",
    "                mass += i\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for x in asteroids:\n",
    "            if x > mass:\n",
    "                return False\n",
    "            mass += x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in asteroids:\n",
    "            print(mass, i)\n",
    "            if mass < i: return False\n",
    "            else: mass += i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for n in asteroids:\n",
    "            if n > mass:\n",
    "                return False\n",
    "            mass += n\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        for ast in sorted(asteroids):\n",
    "            if mass >= ast:\n",
    "                mass += ast\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in range(len(asteroids)):\n",
    "            if mass >= asteroids[i]:\n",
    "                mass += asteroids[i]\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        p, l = 0, len(asteroids)\n",
    "        while p < l and mass >= asteroids[p]:\n",
    "            mass += asteroids[p]\n",
    "            p += 1\n",
    "        return p == l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for x in asteroids:\n",
    "            if mass >= x:\n",
    "                mass += x\n",
    "            else:\n",
    "                 return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        flag = True\n",
    "        for item in asteroids:\n",
    "            if mass < item:\n",
    "                flag = False\n",
    "                break\n",
    "            else:\n",
    "                mass += item\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for value in asteroids:\n",
    "            if mass >= value:\n",
    "                mass += value\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for num in asteroids:\n",
    "            if mass >= num:\n",
    "                mass += num\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for num in asteroids:\n",
    "            if mass >= num:\n",
    "                mass += num\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "\n",
    "        def upper_power2(x):\n",
    "            x |=x>>1\n",
    "            x |=x>>2\n",
    "            x |=x>>4\n",
    "            x |=x>>8\n",
    "            x |=x>>16\n",
    "            x+=1\n",
    "            return x>>1\n",
    "\n",
    "        minh={}\n",
    "        total=defaultdict(int)\n",
    "        for num in asteroids:\n",
    "            h=upper_power2(num)\n",
    "            if minh.get(h,inf)>num:\n",
    "                minh[h]=num\n",
    "            total[h]+=num\n",
    "        for i in range(17):\n",
    "            h=1<<i\n",
    "            if mass<minh.get(h,0):\n",
    "                return False\n",
    "            mass+=total[h]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        sum_dict, min_dict = {}, {}\n",
    "        for num in asteroids:\n",
    "            len_bin_str = len(bin(num)[2:])\n",
    "            sum_dict[len_bin_str] = sum_dict.get(len_bin_str, 0) + num\n",
    "            min_dict[len_bin_str] = min(min_dict.get(len_bin_str, 1e7), num)\n",
    "        for idx in sorted(min_dict.keys()):\n",
    "            if mass < min_dict[idx]:\n",
    "                return False\n",
    "            mass += sum_dict[idx]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for x in asteroids:\n",
    "            if mass < x:\n",
    "                return False\n",
    "            mass += x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for num in asteroids:\n",
    "            if num <= mass:\n",
    "                mass += num\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in asteroids:\n",
    "            if mass < i:\n",
    "                return False\n",
    "            mass += i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in range(len(asteroids)):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        hash_ = [0] * 100001\n",
    "        max_ = 0\n",
    "        min_ = 100001\n",
    "        for num in asteroids:\n",
    "            hash_[num] += 1\n",
    "            max_ = max(num, max_)\n",
    "            min_ = min(num, min_)\n",
    "        if mass < min_:\n",
    "            return False\n",
    "        for m in range(min_, max_ + 1):\n",
    "            if hash_[m] >= 1:\n",
    "                if mass < m:\n",
    "                    return False\n",
    "                else:\n",
    "                    mass += hash_[m] * m\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for aa in asteroids:\n",
    "            if mass<aa:\n",
    "                return False\n",
    "            mass+=aa\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        n=len(asteroids)\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if mass>=asteroids[i]:\n",
    "                mass+=asteroids[i]\n",
    "                c+=1\n",
    "        if c==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "\n",
    "        def upper_power2(x):\n",
    "            x |=x>>1\n",
    "            x |=x>>2\n",
    "            x |=x>>4\n",
    "            x |=x>>8\n",
    "            x |=x>>16\n",
    "            return (x+1)>>1\n",
    "\n",
    "        minh={}\n",
    "        total={}\n",
    "        for num in asteroids:\n",
    "            h=upper_power2(num)\n",
    "            if minh.get(h,inf)>num:\n",
    "                minh[h]=num\n",
    "            total[h]=total.get(h,0)+num\n",
    "        for i in range(17):\n",
    "            h=1<<i\n",
    "            if mass<minh.get(h,0):\n",
    "                return False\n",
    "            mass+=total.get(h,0)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        big = sorted([i for i in asteroids if i > mass])\n",
    "        total = mass + sum([i for i in asteroids if i <= mass])\n",
    "        for i in big:\n",
    "            if i > total:\n",
    "                return False\n",
    "            else:\n",
    "                total += i \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        lst = accumulate(asteroids, initial = mass)\n",
    "        return all(x <= y for x, y in zip(asteroids, lst))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "      asteroids.sort()\n",
    "      for i in asteroids:\n",
    "        if mass >= i:\n",
    "          mass += i\n",
    "        else:\n",
    "          return False\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        v = [0] * 18\n",
    "        s = [0] * 18\n",
    "        n = len(asteroids)\n",
    "        for i in range(0, 18):\n",
    "            v[i] = 100005\n",
    "            s[i] = 0\n",
    "        for num in asteroids:\n",
    "            t = num.bit_length()\n",
    "            v[t] = min(v[t], num)\n",
    "            s[t] = min(s[t] + num, 100005)\n",
    "        for i in range(18):\n",
    "            if v[i] < 100005 and v[i] > mass:\n",
    "                return False\n",
    "            mass += s[i]\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n",
    "        asteroids.sort()\n",
    "        for i in  asteroids:\n",
    "            if mass - i < 0: return False\n",
    "            else: mass += i \n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
